1. Field of the Invention
This invention relates to a data processing system having virtual memory, and relates more particularly to such a system employing overlapped virtual address translation and address computation.
2. Prior Art
It is well known in data processing systems to use a hierarchical memory system which employs a high-access-speed, low-capacity memory as a main memory and a low-access-speed, high-capacity memory as a secondary store. The purpose of the main memory is to provide appropriate transfer rates to and from a processing module, with data and other information being transferred from the secondary store or memory to the main memory as required. A virtual memory system is created by providing a hierarchical memory system with the abililty to automatically transfer requested information from the secondary store to main memory when that information does not reside in main memory at the time of its request. In this manner, the user is not aware of any inherent limitations due to the size of the main memory.
The advantage of a virtual storage implementation is that not all of the stored information, either program or data, needed for the progress of the computation is required to be stored in main memory simultaneously, but that for large periods of time, parts of the stored information may reside in the secondary store. This advantage follows from the fact that main memory is generally more expensive on a per unit or per bit basis than the secondary store.
For virtual memory applications, the information is partitioned into a number of segments such that, during the progress of the computation, the information of a segment will either be totally present in, or totally absent from, the main or primary store. If all the segments have the same size. they are generally referred to as pages, in which case the primary store is then subdivided into so-called page frames which are units of the store able to contain exactly one page.
The random location of segments and pages in main storage necessitates the translation of virtual addresses to actual or real addresses using a set of address translation tables that are located in main storage and conventionally are referred to as page frame tables. In a large virtual system, a great many such address translation tables are employed and may be organized in a number of different ways. The essential feature of any such organization is that the particular virtual address must logically map to a memory location in the tables which will contain the real address for the virtual address.
Functionally, the operation of such address conversion tables is as follows: the high order bits of the particular virtual address are used to access a specific section of the translation tables which relate to a particular frame or segment, whereupon a search is performed on the lower bits to determine if a particular virtual address is contained therein and, if so, what real address is associated therewith. Each page table pointed to by a virtual frame address contains the real locations of all of the pages in one of the frames. Therefore, if a particular frame is divided into, for example, 16 pages, there would be 16 page tables for each frame, and a separate frame table which would have the entries pointing to a particular set of individual page table. It should be understood that the above description is generalized in nature and that there are many different ways of organizing the address conversion utilizing the page tables, as well as the means for addressing the same, starting with the CPU-produced virtual address.
When making the actual address translation, regardless of the details of the overall system organization and use of the page tables, the proper entry point into the page-frame tables is made and the page tables are accessed using the presented virtual address as the argument and, usually after a plurality of memory accesses, the desired entry in the page tables is found. The byte portion of the virtual address or "byte offset" is essentially a relative address and is the same in the virtual page as in the real page, whereby once the desired real page address portion of the virtual address has been translated, the byte offset portion is concatenated onto the real page address location to provide the real byte address in main storage.
As is well known in current virtual memory systems, in order to avoid having to translate a virtual address each time the memory is accessed, translations of recently used virtual addresses to real addresses are retained in a special set of rapidly accessible tables or high speed memories referred to as Directory Look-Aside Tables (DLAT) or Translation Look-Aside Buffers (TLBs). These tables or buffers are conventionally special high speed or rapidly accessible memories which may be accessed much more rapidly than the previously described page frame tables, whereby frequently used virtual addresses may be stored in this table and accessed very rapidly, with a resultant saving of a great deal of execution time within the computer. The efficiency of such TLB address translation systems is predicated upon the fact that, subsequent to the first access to a particular virtual page, there will be a great many accesses to the same page during a given program execution. As indicated above, even though subsequent accesses are to different lines and bytes within a page, the virtual-to-real page address translation is the same for that page regardless of which line or byte is being addressed.
In a microprocessor system which employs virtual addressing, the delay caused by the virtual address translation process limits the time available for load and store accesses to main storage. This impact may be reduced if the microprocessor includes a data cache, since the cache may be accessed in parallel with translation of the virtual address. However, a data cache of sufficient size generally cannot be economically placed on a Very Large Scale Integrated (VLSI) microprocessor. Since the storage access time for operands is a major performance parameter, it is very desirable to have some method of reducing or eliminating the address translation delay from the storage access path even if a data cache is not used.